package seqlist.link.leetcode;

/**
 * @author yuisama
 * @date 2023/03/16 19:32
 * 删除链表的重复元素，重复元素只出现一次
 **/
public class Num83_DeleteDuplicates {
    //    public ListNode deleteDuplicates(ListNode head) {
//        // 1.base case.
//        if (head == null || head.next == null) {
//            return head;
//        }
//        // 2.链表一定有两个节点
//        ListNode dummyHead = new ListNode(-101);
//        dummyHead.next = head;
//        ListNode prev = dummyHead;
//        ListNode cur = prev.next;
//        while (cur != null) {
//            if (prev.val == cur.val) {
//                prev.next = cur.next;
//            }else {
//                prev = prev.next;
//            }
//            cur = cur.next;
//        }
//        return dummyHead.next;
//    }
    // 递归法
    public ListNode deleteDuplicates(ListNode head) {
        // 1.base case
        if (head == null || head.next == null) {
            return head;
        }
        // 先把子链表中所有重复节点删除完毕，只保留一次元素
        head.next = deleteDuplicates(head.next);
        // 现在只剩下头节点
        return head.val == head.next.val ? head.next : head;
    }
}